<?php
/**
 * @title 488. 祖玛游戏
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }


class Solution {

    /**
     * @param String $board
     * @param String $hand
     * @return Integer
     */
    function findMinStep($board, $hand) {
        /**
         * @since 2021/11/10 防止重复
         * @since 2021/11/10 board和hand，不能重复
         */
        $this->hashArray = [];

        /**
         * @since 2021/11/10 统计手上的球，保持顺序
         */
        $ballCntArray = [
            "R" => 0,
            "Y" => 0,
            "B" => 0,
            "G" => 0,
            "W" => 0,
        ];
        for($i=0, $len=strlen($hand); $i<$len; $i++){
            $ballCntArray[$hand[$i]] += 1;
        }

        /**
         * @since 2021/11/11 最小出手次数
         */
        $this->minDeep = 100;

        /**
         * @since 2021/11/11 查找次数
         */
        self::find($board, $ballCntArray, $len, 0);

        /**
         * @since 2021/11/11 未能消除所有球
         */
        if($this->minDeep == 100){
            $this->minDeep = -1;
        } else {}

        /**
         * @return
         */
        return $this->minDeep;
    }

    /**
     * @title 查找消除桌面球，最少球数量
     * @author start2004
     * @since 2021/11/11 Created
     *
     * @param string $board
     * @param string $hand
     * @return int
     */
    public function find($board = '', $ballCntArray = [], $len = 0, $deep = 0){
        /**
         * @since 2021/11/11 手上没有球
         */
        if($len == 0){
            return ;
        } else {}

        /**
         * @since 2021/11/11 剪枝，当前出手次数需要低于全局最小次数
         */
        if($deep < $this->minDeep){
        } else {
            return ;
        }

        /**
         * @since 2021/11/11 桌面上球，切成数组
         */
        // echo "board = {$board}", PHP_EOL;
        $bArray = [""];
        for($i=0; $i<strlen($board); $i++){
            $bArray[] = $board[$i];
            $bArray[] = "";
        }
        // return $bArray;

        /**
         * @since 2021/11/11 尝试每种颜色的球
         */
        foreach ($ballCntArray as $ball=>$cnt){
            if($cnt >= 1){
                /**
                 * @since 2021/11/11 插入颜色的球
                 */
                // echo "ball = {$ball}", PHP_EOL;

                /**
                 * @since 2021/11/11 手上球数量-1
                 */
                $ballCntArray[$ball] -= 1;

                /**
                 * @since 2021/11/11 手上球，key
                 */
                $ballKey = implode("", $ballCntArray) ."-";

                /**
                 * @since 2021/11/11 每个空位都尝试
                 */
                for ($i=0; $i<count($bArray); $i+=2){
                    /**
                     * @since 2021/11/12 如果前后球颜色相同，不能插入另外一个颜色
                     * @since 2021/11/12 比如AA, 不可以插入B，可以插入A
                     */
                    if(isset($bArray[$i-1]) AND isset($bArray[$i+1])){
                        if($bArray[$i-1] == $bArray[$i+1] AND $bArray[$i-1] != $ball){
                            continue;
                        } else {}
                    } else {}
                    
                    
                    /**
                     * @since 2021/11/11 插入空位
                     */
                    // echo "i = ", ($i/2), ", ";
                    $bArray[$i] = $ball;

                    /**
                     * @since 2021/11/11 当前桌面球
                     */
                    $currentBoard = implode("", $bArray);

                    /**
                     * @since 2021/11/11 手上球 加 桌面球，新key
                     */
                    $key = $ballKey . $currentBoard;

                    /**
                     * @since 2021/11/11 是否重复
                     */
                    if(!isset($this->hashArray[$key])){
                        $this->hashArray[$key] = 1;

                        /**
                         * @since 2021/11/11 3个和以上相同颜色的球，合并
                         */
                        // echo "insert = {$currentBoard}, ";
                        $removeBoard = self::remove($currentBoard);
                        // echo "remove = {$removeBoard}", PHP_EOL;

                        /**
                         * @since 2021/11/11 完全消除
                         */
                        if(empty($removeBoard)){
                            /**
                             * @since 2021/11/11 更新最小值
                             */
                            $this->minDeep = min($this->minDeep, $deep+1);
                        } else {
                            /**
                             * @since 2021/11/11 是否重复
                             * @since 2021/11/11 如果并未消除球，则不需要检查重复
                             * @since 2021/11/11 如果消除球，则需要检查是否重复
                             */
                            $key = $ballKey . $removeBoard;
                            if($removeBoard == $currentBoard OR !isset($this->hashArray[$key])){
                                $this->hashArray[$key] = 1;

                                /**
                                 * @since 2021/11/11 递归
                                 */
                                // echo "递归查找, remove={$removeBoard}", PHP_EOL;
                                self::find($removeBoard, $ballCntArray, $len-1, $deep+1);
                            } else {
                                // echo "消除后，重复，remove={$removeBoard}", PHP_EOL;
                            }
                        }
                    } else {
                        // echo "未消除前，重复, insert={$currentBoard}", PHP_EOL;
                    }

                    /**
                     * @since 2021/11/11 空位恢复
                     */
                    $bArray[$i] = "";
                    // echo PHP_EOL;
                }

                /**
                 * @since 2021/11/11 手上球数量+1
                 */
                $ballCntArray[$ball] += 1;
                // echo PHP_EOL;
            } else {}
        }
    }

    /**
     * @title 消除3个和以上相同颜色的球
     * @author start2004
     * @since 2021/11/11 Created
     *
     * @param string $board
     * @return string
     */
    public function remove($board = ''){
        // $b = $board;

        /**
         * @since 2021/11/11 上次颜色相同的球
         */
        $color = "";

        /**
         * @since 2021/11/11 查找颜色相同的球
         */
        for ($i=2; $i<strlen($board); $i++){
            /**
             * @since 2021/11/11 是否已经有连续相同颜色的球
             */
            if(empty($color)){
                /**
                 * @since 2021/11/11 3个连续的球，颜色相同
                 */
                if($board[$i] == $board[$i-1] AND $board[$i] == $board[$i-2]){
                    $color = $board[$i];
                    $board[$i-2] = $board[$i-1] = $board[$i] = "x";
                } else {
                    /**
                     * @since 2021/11/11 不符合要求
                     */
                }
            } else {
                /**
                 * @since 2021/11/11 颜色相同，继续
                 */
                if($board[$i] == $color){
                    $board[$i] = "x";
                } else {
                    /**
                     * @since 2021/11/11 颜色不相同
                     */
                    break;
                }
            }
        }

        /**
         * @since 2021/11/11 发现颜色相同的球
         */
        if(!empty($color)){
            /**
             * @since 2021/11/11 存在颜色相同的球被消除
             */
            $board = str_replace("x", "", $board);

            /**
             * @since 2021/11/11 迭代继续消除
             */
            $board = self::remove($board);
        } else {}

        /**
         * @return
         */
        // echo "board = {$b}, remove = {$board}", PHP_EOL;
        return $board;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202111/2021.11.09.php
 */
$datas = [
    // ["WRRBBW", "RB"], // -1
    // ["WWRRBBWW", "WRBRW"], // 2
    // ["G", "GGGGG"], // 2
    ["RRWWRRBBRR", "WB"], // 2
    // ["RRGGBBYYWWRRGGBB","RGBYW"], // -1
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    if(count($data) <= 20){
        var_dump($data);
    } else {
        var_dump(count($data));
    }

    $obj = new Solution();
    $result = $obj->findMinStep(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
